//力扣437. 路径总和 III
//暴力解法
import java.util.HashMap;
import java.util.Map;
  class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode() {}
      TreeNode(int val) { this.val = val; }
      TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
          this.left = left;
          this.right = right;
      }
  }

class Solution {
    public int pathSum(TreeNode root, int targetSum) {
        if(root==null){
            return 0;
        }
        int res = func(root,targetSum);
        res+=pathSum(root.left,targetSum);
        res+=pathSum(root.right,targetSum);
        return res;
    }
    public int func(TreeNode root,long targetSum){
        int res = 0;
        if(root==null){
            return 0;
        }
        if(root.val == targetSum){
            res++;
        }
        res+=func(root.left,targetSum-root.val);
        res+=func(root.right,targetSum-root.val);
        return res;
    }
}
//前缀和+哈希表解法
class Solution2 {
    public int pathSum(TreeNode root, int targetSum) {
        Map<Long, Integer> prefixSumMap = new HashMap<>();
        prefixSumMap.put(0L, 1); // 初始前缀和为0的路径有1条
        return dfs(root, 0L, targetSum, prefixSumMap);
    }

    private int dfs(TreeNode node, long currSum, int targetSum, Map<Long, Integer> prefixSumMap) {
        if (node == null) {
            return 0;
        }

        currSum += node.val;
        int res = prefixSumMap.getOrDefault(currSum - targetSum, 0); // 这里找currSum - targetSum是因为如果currSum减去currSum - targetSum就等于targetSum了，就找到一条路径了

        prefixSumMap.put(currSum, prefixSumMap.getOrDefault(currSum, 0) + 1);
        res += dfs(node.left, currSum, targetSum, prefixSumMap);
        res += dfs(node.right, currSum, targetSum, prefixSumMap);
        prefixSumMap.put(currSum, prefixSumMap.get(currSum) - 1); // 回溯(相当于删除)

        return res;
    }
}



//124. 二叉树中的最大路径和
class Solution3 {
    private int maxSum = Integer.MIN_VALUE;
    public int maxPathSum(TreeNode root) {
        maxGain(root);
        return maxSum;
    }

    private int maxGain(TreeNode node) {
        if (node == null) {
            return 0;
        }

        // 计算左右子树的最大贡献值（如果是负数则取0）
        int leftGain = Math.max(maxGain(node.left), 0);
        int rightGain = Math.max(maxGain(node.right), 0);

        // 当前节点的路径和（左+根+右），更新全局最大值
        int currentSum = node.val + leftGain + rightGain;
        maxSum = Math.max(maxSum, currentSum);

        // 返回当前节点的最大贡献值（只能选左或右）
        return node.val + Math.max(leftGain, rightGain);
    }
}